from typing import List
import collections

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        """
        计算完成所有任务所需的最短时间间隔
        
        参数:
            tasks: 任务列表，每个任务用大写字母表示
            n: 相同任务之间的冷却时间
        返回:
            完成所有任务所需的最短时间间隔
        """
        # 统计每个任务的频率
        freq = collections.Counter(tasks)
        
        # 任务种类数
        m = len(freq)
        # 记录每个任务下一次可以执行的时间
        nextValid = [1] * m
        # 记录每个任务剩余的次数
        rest = list(freq.values())
        
        time = 0
        for i in range(len(tasks)):
            time += 1
            # 找到所有剩余任务中最早可以执行的时间
            minNextValid = min(nextValid[j] for j in range(m) if rest[j] > 0)
            # 如果当前时间小于最早可执行时间，需要等待
            time = max(time, minNextValid)
            
            # 选择剩余次数最多的任务
            best = -1
            for j in range(m):
                if rest[j] and nextValid[j] <= time:
                    if best == -1 or rest[j] > rest[best]:
                        best = j
            
            # 更新选中任务的下一次可执行时间
            nextValid[best] = time + n + 1
            # 减少选中任务的剩余次数
            rest[best] -= 1
        
        return time 